type Node = {
    x: number;
    y: number;
    g: number; // 从起点到当前节点的实际代价
    h: number; // 从当前节点到终点的预估代价（使用曼哈顿距离）
    f: number; // 总代价，即 g + h
    previous: Node | null; // 前一个节点，用于回溯路径
};

class AStar {
    private grid: number[][];
    private start: Node;
    private end: Node;
    private openSet: Node[];
    private closedSet: Set<string>;

    constructor(grid: number[][], startX: number, startY: number, endX: number, endY: number) {
        this.grid = grid;
        this.start = { x: startX, y: startY, g: 0, h: 0, f: 0, previous: null };
        this.end = { x: endX, y: endY, g: 0, h: 0, f: 0, previous: null };
        this.openSet = [this.start];
        this.closedSet = new Set<string>();
    }

    private heuristic(node: Node): number {
        return Math.abs(node.x - this.end.x) + Math.abs(node.y - this.end.y);
    }

    private nodeToString(node: Node): string {
        return `${node.x},${node.y}`;
    }

    public findPath(): Node[] | null {
        while (this.openSet.length > 0) {
            let currentNode = this.openSet[0];
            for (let i = 1; i < this.openSet.length; i++) {
                if (this.openSet[i].f < currentNode.f || (this.openSet[i].f === currentNode.f && this.openSet[i].h < currentNode.h)) {
                    currentNode = this.openSet[i];
                }
            }

            const currentIndex = this.openSet.indexOf(currentNode);
            this.openSet.splice(currentIndex, 1);
            this.closedSet.add(this.nodeToString(currentNode));

            if (this.nodeToString(currentNode) === this.nodeToString(this.end)) {
                return this.reconstructPath(currentNode);
            }

            for (const neighbor of this.getNeighbors(currentNode)) {
                if (this.closedSet.has(this.nodeToString(neighbor)) || this.grid[neighbor.x][neighbor.y] === 1) {
                    continue;
                }

                const tentativeG = currentNode.g + 1;

                if (!this.openSet.includes(neighbor) || tentativeG < neighbor.g) {
                    neighbor.previous = currentNode;
                    neighbor.g = tentativeG;
                    neighbor.h = this.heuristic(neighbor);
                    neighbor.f = neighbor.g + neighbor.h;

                    if (!this.openSet.includes(neighbor)) {
                        this.openSet.push(neighbor);
                    }
                }
            }
        }

        return null;
    }

    private getNeighbors(node: Node): Node[] {
        const neighbors: Node[] = [];
        const { x, y } = node;

        const directions = [
            { x: 0, y: -1 }, // 上
            { x: 0, y: 1 },  // 下
            { x: -1, y: 0 }, // 左
            { x: 1, y: 0 }   // 右
        ];

        for (const direction of directions) {
            const neighborX = x + direction.x;
            const neighborY = y + direction.y;

            if (neighborX >= 0 && neighborX < this.grid.length &&
                neighborY >= 0 && neighborY < this.grid[0].length) {
                neighbors.push({ x: neighborX, y: neighborY, g: 0, h: 0, f: 0, previous: null });
            }
        }

        return neighbors;
    }

    private reconstructPath(node: Node | null): Node[] {
        const path = [];
        let currentNode = node;

        while (currentNode !== null) {
            path.push(currentNode);
            currentNode = currentNode.previous;
        }

        return path.reverse();
    }
}

export default AStar;